class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        m = len(s1)
        n = len(s2)
        k = len(s3)
        if k != (m + n):
            return False
        else:
            f = [False for _ in range(n + 1)]
            f[0] = True
            for i in range(m + 1):
                for j in range(n + 1):
                    if i > 0:
                        f[j] = f[j] and (s1[i - 1] == s3[i + j - 1])
                    if j > 0:
                        f[j] = f[j] or (f[j - 1] and s2[j - 1] == s3[i + j - 1])
        return f[-1]


data = Solution()
s1 = "aacaac"
s2 = "aacaaeaac"
s3 = "aacaaeaaeaacaac"
print(data.isInterleave(s1, s2, s3))
